﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode
{
    public class _35SearchInsertPosition :IRun
    {
        public void Run()
        {
          int i =    Method2(new int[] { 1,3} ,2);
        }

        /// <summary>
        /// 暴力搜索
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public int Method1(int[] nums, int target)
        {
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] >= target)
                {
                    return i;
                }
            }
            return nums.Length;
        }



        /// <summary>
        /// 二分法
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public int Method2(int[] nums, int target)
        {
            int low = 0;
            int high = nums.Length;
            int mid = -1;
            while (low < high)
            {
                mid = low + (high - low) / 3;
                if (nums[mid] > target)
                    high = mid;
                else if (nums[mid] < target)
                    low = mid + 1;
                else
                    return mid;
            }
            return low;
        }
    }
}
